package com.cty.C_SortAlgorithms.D_ShellSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/17 15:49
 * @Description: 希尔排序  基于数组实现
 * @version: 1.0
 */
public class ShellSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public ShellSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 在数组尾部插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }

    /**
     * 希尔排序
     *      时间复杂度：    O(N^(7/6) ~ N^(3/2))    受数据分布影响，理论上难分析，主要来自于试验评估
     *      空间复杂度：    O(1)                    不需要额外空间辅助
     *      排序方式：                              内部排序
     *      稳定性：                                不稳定    存在跳跃式交换
     * 起因：
     *      初始时若一个比较小的数靠近序列的尾部，由于是一步一步的比较移动，因此使用插入排序会移动（或复制）很多次。
     *      解决：开始时先使用比较大的步子排序使序列“基本有序”，最后再使用插入排序——希尔排序
     * 间隔（步子）：
     *      选择：间隔序列中的数字互质很重要，可以使每一趟排序更有可能保持前一趟已排好的效果。
     *      常用：h = h*3 + 1
     */
    public void shellSort(){
        // 获取间隔队列
        int h = 1;
        while(h < nItems/3)  // nItems/3 是保证最后的h是小于nItems的
            h = h*3 + 1;

        // 希尔排序
        while(h > 0){
            int in, out;
            for(out=h; out<nItems; out++){
                DataItem temp = array[out].getItem();
                in = out;
                while(in>h-1 && array[in-h].getKey() >= temp.getKey()){
                    array[in].setItem(array[in-h]);
                    in -= h;
                }
                array[in] = temp;
            }  // end for
            h = (h - 1) / 3;  // 最后一次 h=1，变成插入排序
        }  // end while
    }  // end shellSort()













    // 练习 希尔排序


}  // end ShellSort{}
